package main

import "fmt"

type ListNode struct{
	value int
	Next *ListNode
}
//3->3->2->1
//双指针实现链表 原地反转 时间复杂度O(n)
func reverseList(head *ListNode) *ListNode {
	//
	var prev *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = prev
		prev = cur
		cur = next
	}
	return prev
}

//1->2->3->4->5
//使用递归的方法实现链表反转 时间复杂度O(n)
//func reverseList(head *ListNode) *ListNode{
//	//直到当前节点的下一个节点为空时返回当前节点  递归终止条件
//	if head == nil || head.Next == nil{
//		return head
//	}
//	newHead := reverseList(head.Next)
//	head.Next.Next = head
//	head.Next = nil
//	return newHead
//}

//还可以使用头插法完成反转链表，浪费太多空间



func main(){

	l5 := ListNode{
		value: 5,
		Next: nil,

	}
	l4 := ListNode{
		value: 4,
		Next: &l5,

	}
	l3 := ListNode{
		value: 3,
		Next: &l4,

	}
	l2 := ListNode{
		value: 2,
		Next: &l3,

	}
	l1 := ListNode{
		value: 1,
		Next: &l2,

	}
	L := reverseList(&l1)
	for L != nil{
		fmt.Printf("%d->",L.value)
		L = L.Next
	}
}